/*
 * Nancy Qiannan Zhang
 * Andrew ID: qiannanz
 * 
 * Mita Yipeng Yun
 * Andrew ID: yipengy
 */

package edu.cmu.cs211.bacon.kevin;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Map;
import java.util.List;
import edu.cmu.cs211.bacon.util.Dijkstra;
import edu.cmu.cs211.bacon.util.Edge;
import edu.cmu.cs211.bacon.util.GeneralGraph;

/**
 * 
 * Given a map of people and the movies they've appeared in, creates a 
 * single-source shortest-paths solution for the Kevin Bacon game (or for
 * any other actor or actress provided as the source).  
 *
 */
public class KevinBaconGameSolver {
	private GeneralGraph<String, Edge<String>> g;
	private String s;	// source
    
	public KevinBaconGameSolver(String s, GeneralGraph<String, Edge<String>> g)
	{
		this.s = s;
		this.g = g;
	}
    /** 
     * Constructs, runs single-source shortest paths, and returns a solution
     * to the weighted version of the Kevin Bacon Game, from a specified starting
     * point.  The weighted version of the game is as described in the assignment
     * documentation, with the weight of an edge being 2011 - m.year if two people
     * most recently appeared in movie m.
     * 
     * @param source
     *      The person from which to compute shortest paths. For example, the 
     *      source would be "Bacon, Kevin" to compute solutions to the 
     *      unweighted version of the Kevin Bacon game for Kevin Bacon.
     *      
     * @param movieMap
     *      A map between people and the movies they appeared in.  You can create
     *      simple maps on your own for testing purposes (please do), or read
     *      the maps from the sample movie files we provided.
     *      
     * @return
     *      A solution to the single-source shortest paths problem for the 
     *      specified source and movie map.
     *      
     * @throws NullPointerException
     *      If source or movieMap is null.
     */
    public static KevinBaconGameSolver 
      createWeightedGameSolver(String source, Map<String, List<Movie>> movieMap) {
    	if(source == null || movieMap == null)
			throw new NullPointerException();
    	
    	/*
    	 * create graph:
    	 * vertex: person
    	 * edge: if 2 people share the same movie
    	 * weight of edge: 2011 - m.year
    	 */
    	Collection<String> names = movieMap.keySet();
    	// build graph out of vertex set
    	GeneralGraph<String, Edge<String>> g = new GeneralGraph<String, Edge<String>>(names);
    	// then add source
    	g.addVertex(source);
    	// add edges
    	for(String s: names)
    	{
    		// get the movie list of the current person
    		ArrayList<Movie> curmovies = new ArrayList<Movie>(movieMap.get(s));
    		// walk down the movie list, search every item in all other people's movie lists
    		for(Movie m: curmovies)
    		{
    			for(String look: names)
    			{
    				if(!look.equals(s))
    				{
    					// if m is in a common movie between s and look
    					if(movieMap.get(look).contains(m))
    					{
    						// if there already exists an edge
    						if(g.connected(s, look) != null)
    						{
    							Edge<String> dup = g.connected(s, look);
    							// only update if new coming movie is newer than the prev one
    							if(dup.weight() > (2011-m.getYear()))
    							{
    								g.outgoingEdges(s).remove(dup);
    							}
    						}
    						// add new edge between s and look
    						Edge<String> e = new Edge<String>(s, look, 2011-m.getYear());
							g.addEdge(e);
    					}
    				}
    			}
    		}
    	}
    	return new KevinBaconGameSolver(source, g);
    }

    /** 
     * Constructs, runs single-source shortest paths, and returns a solution
     * to the traditional unweighted version of the Kevin Bacon Game, from a 
     * specified starting point.  
     * 
     * @param source
     *      The person from which to compute shortest paths. For example, the 
     *      source would be "Bacon, Kevin" to compute solutions to the 
     *      unweighted version of the Kevin Bacon game for Kevin Bacon.
     *      
     * @param movieMap
     *      A map between people and the movies they appeared in.  You can create
     *      simple maps on your own for testing purposes (please do), or read
     *      the maps from the sample movie files we provided.
     *      
     * @return
     *      A solution to the single-source shortest paths problem for the 
     *      specified source and movie map.
     *      
     * @throws NullPointerException
     *      If source or movieMap is null.
     */

    public static KevinBaconGameSolver 
      createUnweightedGameSolver(String source, Map<String, List<Movie>> movieMap) {
    	if(source == null || movieMap == null)
			throw new NullPointerException();
    	
    	/*
    	 * create graph:
    	 * vertex: person
    	 * edge: if 2 people share the same movie
    	 * weight of edge: 2011 - m.year
    	 */
    	Collection<String> names = movieMap.keySet();
    	// build graph out of vertex set
    	GeneralGraph<String, Edge<String>> g = new GeneralGraph<String, Edge<String>>(names);
    	// then add source
    	g.addVertex(source);
    	// add edges
    	for(String s: names)
    	{
    		// get the movie list of the current person
    		ArrayList<Movie> curmovies = new ArrayList<Movie>(movieMap.get(s));
    		// walk down the movie list, search every item in all other people's movie lists
    		for(Movie m: curmovies)
    		{
    			for(String look: names)
    			{
    				if(!look.equals(s))
    				{
    					// if m is in a common movie between s and look
    					if(movieMap.get(look).contains(m))
    					{
    						// since it's unweighted, only update when s and look are not connected
    						if(g.connected(s, look) == null)
    						{
    							// add new edge between s and look
        						Edge<String> e = new Edge<String>(s, look, 1);
    							g.addEdge(e);
    						}
    					}
    				}
    			}
    		}
    	}
    	return new KevinBaconGameSolver(source, g);
    }
    
    /**
     * 
     * @param dest
     *      The destination to which to compute a shortest path.
     *      
     * @return
     *      An in-order list of the actors/actresses in the shortest path,
     *      including the source and destination people, starting from the
     *      source, or null if there is no path.  
     *      Each item in this list should just be the string name 
     *      of the actor or actress, not the movie information in which the 
     *      adjacent persons co-appeared.  This function should be either 
     *      O(1) or O(path-length) after the KevinBaconGameSolver is 
     *      constructed and returned.
     *      
     * @throws NullPointerException
     *      If dest is null.
     */
    public List<String> computePath(String dest) {
    	// use dijkstra's algo to compute the shortest path
    	Dijkstra d = new Dijkstra();
    	List<Edge<String>> a =  d.shortestPath(g, s, dest);
    	List<String> result = new ArrayList<String>();
    	// convert every edge into string
    	for(Edge<String> e: a)
    	{
    		result.add(e.toString());
    	}
    	return result;
    }

    /**
     * 
     * @param dest
     *      The destination to which to compute a shortest path.
     *      
     * @return
     *      The length of a shortest path between the source and destination, or 
     *      Double.POSITIVE_INFINITY if there is no path. 
     *      This function should be either O(1) or O(path-length) after the 
     *      KevinBaconGameSolver is constructed and returned.
     *      
     * @throws NullPointerException
     *      If dest is null.
     */
    public double computeDistance(String dest) {
    	if(dest.equals(s))
    		return (double)0;
    	Dijkstra d = new Dijkstra();
    	List<Edge<String>> a =  new ArrayList<Edge<String>>();
    	a.addAll(d.shortestPath(g, s, dest));
    	double result = 0;
    	// walk thru the result edge list and update the total weight
    	for(Edge<String> e: a)
    	{
    		result += e.weight();
    	}
    	return result;
    }
    
    public GeneralGraph<String, Edge<String>> getGraph()
    {
    	return g;
    }
}
